public class LinkedList implements ILinkedListOperation{

    private int size;
    // 维护头尾节点，便于头插尾插
    private ChainNode head;
    private ChainNode tail;

    static class ChainNode {
        public int val;
        public ChainNode next;

        public ChainNode(int val) {
            this.val = val;
        }
    }

    public boolean isEmpty() {
        /**
         * 判空*/
        return size == 0;
    }

    public int size() {
        /**
         * 获取列表元素个数*/
        return size;
    }

    public void add(int val) {
        /**
         * 尾插*/
        // 1 判空
        if(isEmpty()) {
            head = new ChainNode(val);
            tail = head;
            size ++;
            return;
        }
        // 2 不为空时，尾插
        tail.next = new ChainNode(val);
        tail = tail.next;
        size ++;
    }

    public void addFirst(int val) {
        /**
         * 头插*/
        // 1 判空
        if(isEmpty()) {
            head = new ChainNode(val);
            tail = head;
            size ++;
            return;
        }
        // 2 不为空时，头插
        ChainNode tempNode = new ChainNode(val);
        tempNode.next = head;
        head = tempNode;
        size ++;
    }

    public void addLast(int val) {
        /**
         * 尾插*/
        add(val);
    }

    public void addIndex(int index, int val) {
        /**
         * 任意位置插入（下标从0计数）*/
        // 1 校验下标（index==size时为尾插）
        if(index > size || index < 0) {
            throw new IndexOutBoundsException("非法索引：" + index + "，请检查后重试！");
        }
        // 2 特殊位置插入判断
        if(index == 0) {
            addFirst(val);
            return;
        }
        if(index == size) {
            addLast(val);
            return;
        }

        // 3 非头插非尾插情况
        int i = 0;
        ChainNode cur = head;
        ChainNode prev = null;
        while(true) {
            // -找到目标插入位置
            if(i == index) {
                ChainNode tempNode = new ChainNode(val);
                prev.next = tempNode;
                tempNode.next = cur;
                size ++;
                return;
            }
            i++;
            prev = cur;
            cur = cur.next;
        }
    }

    public void remove(int key) {
        /**
         * 删除第一个值为key的节点（从左至右）
         *  查找逻辑：
         *      使用两个变量prev和cur，cur用于遍历链表，prev用于记录前一个节点
         *      1，为头：head = head.next; ==> 避免了prev为空的情况
         *      2，为尾：正常中间逻辑
         *      3，为中间：prev.next = cur.next;
         *  返回值：
         *      设置成void比较好，若是成功删除则正常；若是链表中没有目标值，那就将其视作成功删除，如此就无需返回boolean类型*/
        // 1 判空
        if(isEmpty()) {
            return;
        }
        // 2 遍历查找
        ChainNode cur = head;
        ChainNode prev = null;
        while(cur != null) {
            if(cur.val == key) {
                // -判断是否为头节点
                if(cur == head) {
                    head = head.next;
                    return;
                }
                // -不为，则正常删除
                prev.next = cur.next;
                // -维护尾节点
                if(prev.next == null) {
                    tail = prev;
                }
                return;
            }
            // -正常步进
            prev = cur;
            cur = cur.next;
        }
    }

    public void removeAll(int key) {
        /**
         * 删除所有值为key的节点*/
        // 1 判空
        if(isEmpty()) {
            return;
        }
        // 2 遍历查找
        ChainNode cur = head;
        ChainNode prev = null;
        while(cur != null) {
            if(cur.val == key) {
                if(cur == head) {
                    // -判断是否为头节点
                    head = head.next;
                } else {
                    // -不为，则正常删除
                    prev.next = cur.next;
                    // -维护尾节点
                    if(prev.next == null) {
                        tail = prev;
                    }
                }
                cur = cur.next;
            } else {
                // -未删除时，需维护前节点
                prev = cur;
                cur = cur.next;
            }
        }
    }

    public void clear() {
        /**
         * 删除链表
         * - 无需逐个释放节点，因为是单向链表*/
        head = null;
        tail = null;
        size = 0;
    }

    public void display() {
        /**
         * 打印链表*/
        ChainNode cur = head;
        while(cur != null) {
            System.out.print(cur.val + " ");
            cur =  cur.next;
        }
        System.out.println();
    }
}
